/*
    n源最短路
*/

#include<bits/stdc++.h>
using namespace std;

const int N = 210;
int f[N][N];
int n, m, k;

void floyd(){

/*
 1 - n
    a[1][n] = a[1][1] + a[1][n], a[1][2] + a[2][n], a[1][3] + a[3][n];

    // 
    a[2][n] = a[2][1] + a[1][n], a[2][3] + a[3][n], a[2][4] + a[4][n];

    
    会有依赖问题, 也就是说, a[2][n]可以影响到a[1][n], 但是a[1][n]一开始就写死了, 所以不能把q放在里面
    
    q放在外面
    每次大循环每个点都能被更新到



*/

    for (int q = 1; q <= n; q++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++){
                    f[i][j] = min(f[i][q] + f[q][j], f[i][j]);
            }
}
int main(){
    cin >> n >> m >> k;
    memset(f, 0x3f, sizeof f);
    for (int i = 1; i <= n; i++) f[i][i] = 0;
    for (int i = 1; i <= m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        f[a][b] = min(f[a][b], c);
    }
    floyd();
    for (int i = 1; i <= k; i++){
        int a, b;
        cin >> a >> b;
        if (f[a][b] < 0x3f3f3f3f/2) cout << f[a][b] << endl;
        else cout << "impossible" << endl;
    }
}